实验吧 CTF 编程题 （六）

十九：两个最大子串和

一开始以为是连续子串和，并且没看对题目，没对搞蒙了都，非连续的就很简单判断是否为最大的就是从第一个数就开始往上加，大于就加入，小于就不管，继续找下一个数。两个最大就是将原子串一分为二分别找最大就好了。但还是提交不对，可能是我get不到这个点吧。给出网上的

#include   
using namespace std;
const int INF = -0xfffffff;
const int Max = 100000;

int n;
int b[Max + 2];
int m1[Max + 2], m2[Max + 2]; // m1[i]:Max sum of sub array [0,i] of a  
								  // m2[i]:Max sum of sub array [i,n-1] of a  
int maxSum; // res  
int a[] = { -132,133,134,-11,12,-139,-140,62,63,-64,65,66,67,1,2,3,4,5,-6,7,-48,-49,50,138,16,17,20,101,102,-103,104,-105,106,146,147,148,-107,108,109,110,96,21,-22,23,-24,-25,25,-27,-28,-29,30,41,-42,8,9,10,-46,-47,51,52,-53,54,-55,-56,57,-58,59,60,73,-74,75,-71,-72,18,-97,-98,19,-129,130,-137,136,-13,14,144,-145,15,128,77,-78,-31,32,35,-76,149,-150,99,100,119,91,-92,-93,94,95,116,117,114,118,120,81,82,83,-84,85,-122,-123,112,111,-43,44,45,-113,-115,36,-37,-38,39,40,25,126,127,131,-135,61,-69,70,141,-142,143,-86,68,-87,-90,121,-88,89,-124,-179,-80,-33,34 };

int main()
{
	int n = sizeof(a) / sizeof(a[0]);
	m1[0] = m2[n + 1] = INF;
	memset(b, 0, sizeof(b));
	for (int i = 1; i <= n; ++i) 
	{
		if (b[i - 1] >= 0)
			b[i] = b[i - 1] + a[i];
		else
			b[i] = a[i];
		m1[i] = b[i] > m1[i - 1] ? b[i] : m1[i - 1];
	}
	for (int i = n; i >= 1; --i) 
	{
		if (b[i + 1] >= 0)
			b[i] = b[i + 1] + a[i];
		else
			b[i] = a[i];
		m2[i] = b[i] > m2[i + 1] ? b[i] : m2[i + 1];
	}
	maxSum = INF;
	for (int i = 1; i < n; ++i) 
	{
		if (m1[i] + m2[i + 1] > maxSum)
			maxSum = m1[i] + m2[i + 1];
	}
	printf("%d\n", maxSum);
	return 0;
}

就是用数组保存前几项最大值，和后几项最大值，循环加起来就好，但我觉得最后应该是两重循环。不仅仅是i+1，应当包括i-n所有的。
二十：分数拆分
根据X>Y推算出Y范围，进而确定X

#include 
int main()
{
    int sum=0;
	for(int y=201;y<=600;y++){
		if(400*y%(y-200)==0){
            sum++;
			int x = 400*y/(y-200);
			printf("1/%d = 1/%d + 1/%d\n",400,x,2*y);
			}
		}
		printf("%d",sum);
		return 0;
	}